package demon1;

public class BinarySerachTree {
    public static class Node{
        public int key;
        public Node left;
        public Node right;
        public Node(int key){
            this.key=key;
        }
    }
    public Node root=null;
    public Node search(int val){
        Node cur=root;
        if(root.key==val){
            return cur;
        }
        if(root.key<val){
            cur=cur.right;
        }else if(root.key>val){
            cur=cur.left;
        }
        return null;
    }
    public boolean insert(int val){
        Node cur=root;
        if(root==null){
            Node node =new Node(val);
            root=node;
            return true;
        }
        Node parent=null;
        while(cur!=null){
            if(cur.key==val){
                return true;
            }
            if(cur.key<val){
                parent=cur;
                cur=cur.left;
            }else {
                parent=cur;
                cur=cur.right;
            }
        }
        Node node =new Node(val);
        if(val<parent.key){
            parent.left=node;
        }else{
            parent.right=node;
        }
        return true;
    }


    public void removeNode(int key){
        Node cur=root;
        if(cur==null){
            return;
        }
        Node parent=null;
        while(cur!=null){
            if(cur.key==key){
                remove(parent,cur);
            }else if(cur.key<key){
                parent=cur;
                cur=cur.right;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
    }
    public void remove(Node parent,Node cur){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else if(cur==parent.right){
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.right){
                parent.right=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }
        }else{
            Node targetP=cur;
            Node target=cur.right;
            while(target.left!=null){
                targetP=target;
                target=targetP.left;
            }
            cur.key=target.key;
            if(target==targetP.left){
                targetP.left=target.right;
            }else{
                targetP.right=target.right;
            }

        }
    }
}
